﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GenericLibrary.Common {
    #region MyRegion
    // Stephen Toub
    // stoub@microsoft.com
    // 
    // PriorityQueue.cs
    // A C# implementation of a max priority queue.
    //
    // HISTORY:
    // v1.0.0 - Original version
    // 
    // October 4th, 2002
    // v1.0.0

    // Stephen Toub
    // stoub@microsoft.com
    // 
    // BinaryHeap.cs
    // A C# implementation of a max binary heap.
    //
    // HISTORY:
    // v1.0.0 - Original version
    // 
    // October 4th, 2002
    // v1.0.0

    /// <summary>Collection implemented with the properties of a binary heap.</summary>
    public class BinaryHeap : ICollection, ICloneable {
        #region Member Variables
        /// <summary>The underlying array for the heap (ArrayList gives us resizing capability).</summary>
        private ArrayList _list;
        #endregion

        #region Construction
        /// <summary>Initialize the heap with another heap.</summary>
        /// <param name="heap">The heap on which to perform a shallow-copy.</param>
        public BinaryHeap(BinaryHeap heap) {
            // Clone the list (the only state we have)
            _list = (ArrayList)heap._list.Clone();
        }

        /// <summary>Initialize the heap.</summary>
        /// <param name="capacity">The initial size of the heap.</param>
        public BinaryHeap(int capacity) { _list = new ArrayList(capacity); }

        /// <summary>Initialize the heap.</summary>
        public BinaryHeap() { _list = new ArrayList(); }
        #endregion

        #region Methods
        /// <summary>Empties the heap.</summary>
        public virtual void Clear() { _list.Clear(); }

        /// <summary>Performs a shallow-copy of the heap.</summary>
        /// <returns>A shallow-copy of the heap.</returns>
        public virtual BinaryHeap Clone() { return new BinaryHeap(this); }

        /// <summary>Determines whether an object is in the heap.</summary>
        /// <param name="value">The object for which we want to search.</param>
        /// <returns>Whether the object is in the heap.</returns>
        public virtual bool Contains(object value) {
            foreach(BinaryHeapEntry entry in _list) {
                if(entry.Value == value) return true;
            }
            return false;
        }

        /// <summary>Adds an item to the heap.</summary>
        /// <param name="key">The key for this entry.</param>
        /// <param name="value">The value for this entry.</param>
        public virtual void Insert(IComparable key, object value) {
            // Create the entry based on the provided key and value
            BinaryHeapEntry entry = new BinaryHeapEntry(key, value);

            // Add the item to the list, making sure to keep track of where it was added.
            int pos = _list.Add(entry); // don't actually need it inserted yet, but want to make sure there's enough space for it

            // If it was added at the beginning, i.e. this is the only item, we're done.
            if(pos == 0) return;

            // Otherwise, perform log(n) operations, walking up the tree, swapping
            // where necessary based on key values
            while(pos > 0) {
                // Get the next position to check
                int nextPos = pos / 2;

                // Extract the entry at the next position
                BinaryHeapEntry toCheck = (BinaryHeapEntry)_list[nextPos];

                // Compare that entry to our new one.  If our entry has a larger key, move it up.
                // Otherwise, we're done.
                if(entry.CompareTo(toCheck) > 0) {
                    _list[pos] = toCheck;
                    pos = nextPos;
                } else break;
            }

            // Make sure we put this entry back in, just in case
            _list[pos] = entry;
        }

        /// <summary>Removes the entry at the top of the heap.</summary>
        /// <returns>The removed entry.</returns>
        public virtual object Remove() {
            // Get the first item and save it for later (this is what will be returned).
            if(_list.Count == 0) throw new InvalidOperationException("Cannot remove an item from the heap as it is empty.");
            object toReturn = ((BinaryHeapEntry)_list[0]).Value;

            // Remove the first item
            _list.RemoveAt(0);

            // See if we can stop now (if there's only one item or we're empty, we're done)
            if(_list.Count > 1) {
                // Move the last element to the beginning
                _list.Insert(0, _list[_list.Count - 1]);
                _list.RemoveAt(_list.Count - 1);

                // Start reheapify
                int current = 0, possibleSwap = 0;

                // Keep going until the tree is a heap
                while(true) {
                    // Get the positions of the node's children
                    int leftChildPos = 2 * current + 1;
                    int rightChildPos = leftChildPos + 1;

                    // Should we swap with the left child?
                    if(leftChildPos < _list.Count) {
                        // Get the two entries to compare (node and its left child)
                        BinaryHeapEntry entry1 = (BinaryHeapEntry)_list[current];
                        BinaryHeapEntry entry2 = (BinaryHeapEntry)_list[leftChildPos];

                        // If the child has a higher key than the parent, set that as a possible swap
                        if(entry2.CompareTo(entry1) > 0) possibleSwap = leftChildPos;
                    } else break; // if can't swap this, we're done

                    // Should we swap with the right child?  Note that now we check with the possible swap
                    // position (which might be current and might be left child).
                    if(rightChildPos < _list.Count) {
                        // Get the two entries to compare (node and its left child)
                        BinaryHeapEntry entry1 = (BinaryHeapEntry)_list[possibleSwap];
                        BinaryHeapEntry entry2 = (BinaryHeapEntry)_list[rightChildPos];

                        // If the child has a higher key than the parent, set that as a possible swap
                        if(entry2.CompareTo(entry1) > 0) possibleSwap = rightChildPos;
                    }

                    // Now swap current and possible swap if necessary
                    if(current != possibleSwap) {
                        object temp = _list[current];
                        _list[current] = _list[possibleSwap];
                        _list[possibleSwap] = temp;
                    } else break; // if nothing to swap, we're done

                    // Update current to the location of the swap
                    current = possibleSwap;
                }
            }

            // Return the item from the heap
            return toReturn;
        }
        #endregion

        #region Implementation of ICloneable
        /// <summary>Performs a shallow-copy of the heap.</summary>
        /// <returns>A shallow-copy of the heap.</returns>
        object ICloneable.Clone() { return Clone(); }
        #endregion

        #region Implementation of ICollection
        /// <summary>Copies the entire heap to a compatible one-dimensional array, starting at the given index.</summary>
        /// <param name="array">The array to which the heap should be copied.</param>
        /// <param name="index">The starting index.</param>
        public virtual void CopyTo(System.Array array, int index) {
            _list.CopyTo(array, index);
        }

        /// <summary>Gets a value indicating whether this heap is synchronized.</summary>
        public virtual bool IsSynchronized { get { return false; } }

        /// <summary>Gets the number of objects stored in the heap.</summary>
        public virtual int Count { get { return _list.Count; } }

        /// <summary>Gets an object which can be locked in order to synchronize this class.</summary>
        public object SyncRoot { get { return this; } }
        #endregion

        #region Implementation of IEnumerable
        /// <summary>Gets an enumerator for the heap.</summary>
        /// <returns>An enumerator for all elements of the heap.</returns>
        public virtual IEnumerator GetEnumerator() {
            return new BinaryHeapEnumerator(_list.GetEnumerator());
        }

        /// <summary>Enumerator for entries in the heap.</summary>
        public class BinaryHeapEnumerator : IEnumerator {
            #region Member Variables
            /// <summary>The enumerator of the array list containing BinaryHeapEntry objects.</summary>
            private IEnumerator _enumerator;
            #endregion

            #region Construction
            /// <summary>Initialize the enumerator</summary>
            /// <param name="enumerator">The array list enumerator.</param>
            internal BinaryHeapEnumerator(IEnumerator enumerator) {
                _enumerator = enumerator;
            }
            #endregion

            #region Implementation of IEnumerator
            /// <summary>Resets the enumerator.</summary>
            public void Reset() { _enumerator.Reset(); }

            /// <summary>Moves to the next item in the list.</summary>
            /// <returns>Whether there are more items in the list.</returns>
            public bool MoveNext() { return _enumerator.MoveNext(); }

            /// <summary>Gets the current object in the list.</summary>
            public object Current {
                get {
                    // Returns the value from the entry if it exists; otherwise, null.
                    BinaryHeapEntry entry = _enumerator.Current as BinaryHeapEntry;
                    return entry != null ? entry.Value : null;
                }
            }
            #endregion
        }
        #endregion

        #region Synchronization
        /// <summary>Ensures that heap is wrapped in a synchronous wrapper.</summary>
        /// <param name="heap">The heap to be wrapped.</param>
        /// <returns>A synchronized wrapper for the heap.</returns>
        public static BinaryHeap Synchronize(BinaryHeap heap) {
            // Create a synchronization wrapper around the heap and return it.
            if(heap is SyncBinaryHeap) return heap;
            return new SyncBinaryHeap(heap);
        }

        #endregion

        /// <summary>Represents an entry in a binary heap.</summary>
        private class BinaryHeapEntry : IComparable, ICloneable {
            #region Member Variables
            /// <summary>The key for this entry.</summary>
            private IComparable _key;
            /// <summary>The value for this entry.</summary>
            private object _value;
            #endregion

            #region Construction
            /// <summary>Initializes an entry to be used in a binary heap.</summary>
            /// <param name="key">The key for this entry.</param>
            /// <param name="value">The value for this entry.</param>
            public BinaryHeapEntry(IComparable key, object value) {
                _key = key;
                _value = value;
            }
            #endregion

            #region Properties
            /// <summary>Gets the key for this entry.</summary>
            public IComparable Key { get { return _key; } set { _key = value; } }
            /// <summary>Gets the value for this entry.</summary>
            public object Value { get { return _value; } set { _value = value; } }
            #endregion

            #region Implementation of IComparable
            /// <summary>Compares the current instance with another object of the same type.</summary>
            /// <param name="entry">An object to compare with this instance.</param>
            /// <returns>
            /// Less than 0 if this instance is less than the argument,
            /// 0 if the instances are equal,
            /// Greater than 0 if this instance is greater than the argument.
            /// </returns>
            public int CompareTo(BinaryHeapEntry entry) {
                // Make sure we have valid arguments.
                if(entry == null) throw new ArgumentNullException("entry", "Cannot compare to a null value.");

                // Compare the keys
                return _key.CompareTo(entry.Key);
            }

            /// <summary>Compares the current instance with another object of the same type.</summary>
            /// <param name="obj">An object to compare with this instance.</param>
            /// <returns>
            /// Less than 0 if this instance is less than the argument,
            /// 0 if the instances are equal,
            /// Greater than 0 if this instance is greater than the argument.
            /// </returns>
            int IComparable.CompareTo(object obj) {
                // Make sure we have valid arguments, then compare.
                if(!(obj is BinaryHeapEntry)) throw new ArgumentException("Object is not a BinaryHeapEntry", "obj");
                return CompareTo((BinaryHeapEntry)obj);
            }
            #endregion

            #region Implementation of ICloneable
            /// <summary>Shallow-copy of the object.</summary>
            /// <returns>A shallow-copy of the object.</returns>
            public BinaryHeapEntry Clone() {
                return new BinaryHeapEntry(_key, _value);
            }

            /// <summary>Shallow-copy of the object.</summary>
            /// <returns>A shallow-copy of the object.</returns>
            object ICloneable.Clone() {
                return Clone();
            }
            #endregion
        }

        /// <summary>A synchronized BinaryHeap.</summary>
        public class SyncBinaryHeap : BinaryHeap {
            #region Member Variables
            /// <summary>The heap to synchronize.</summary>
            private BinaryHeap _heap;
            #endregion

            #region Construction
            /// <summary>Initialize the synchronized heap.</summary>
            /// <param name="heap">The heap to synchronize.</param>
            internal SyncBinaryHeap(BinaryHeap heap) { _heap = heap; }
            #endregion

            #region Methods
            /// <summary>Performs a shallow-copy of the heap.</summary>
            /// <returns>A shallow-copy of the heap.</returns>
            public override BinaryHeap Clone() {
                lock(_heap.SyncRoot) return _heap.Clone();
            }

            /// <summary>Empties the heap.</summary>
            public override void Clear() {
                lock(_heap.SyncRoot) _heap.Clear();
            }

            /// <summary>Determines whether an object is in the heap.</summary>
            /// <param name="value">The object for which we want to search.</param>
            /// <returns>Whether the object is in the heap.</returns>
            public override bool Contains(object value) {
                lock(_heap.SyncRoot) return _heap.Contains(value);
            }

            /// <summary>Adds an item to the heap.</summary>
            /// <param name="key">The key for this entry.</param>
            /// <param name="value">The value for this entry.</param>
            public override void Insert(IComparable key, object value) {
                lock(_heap.SyncRoot) _heap.Insert(key, value);
            }

            /// <summary>Removes the entry at the top of the heap.</summary>
            /// <returns>The removed entry.</returns>
            public override object Remove() {
                lock(_heap.SyncRoot) return _heap.Remove();
            }

            /// <summary>Copies the entire heap to a compatible one-dimensional array, starting at the given index.</summary>
            /// <param name="array">The array to which the heap should be copied.</param>
            /// <param name="index">The starting index.</param>
            public override void CopyTo(System.Array array, int index) {
                lock(_heap.SyncRoot) _heap.CopyTo(array, index);
            }

            /// <summary>Gets a value indicating whether this heap is synchronized.</summary>
            public override bool IsSynchronized {
                get { return true; }
            }

            /// <summary>Gets the number of objects stored in the heap.</summary>
            public override int Count {
                get { lock(_heap.SyncRoot) return _heap.Count; }
            }
            /// <summary>Gets an enumerator for the heap.</summary>
            /// <returns>An enumerator for all elements of the heap.</returns>
            public override IEnumerator GetEnumerator() {
                lock(_heap.SyncRoot) return _heap.GetEnumerator();
            }
            #endregion
        }
    }

    /// <summary>A priority queue.</summary>
    public class PriorityQueue : ICollection {
        #region Member Variables
        /// <summary>The binary heap on which the priority queue is based.</summary>
        private BinaryHeap _heap;
        #endregion

        #region Construction
        /// <summary>Initialize the queue.</summary>
        public PriorityQueue() { _heap = new BinaryHeap(); }

        /// <summary>Initialize the queue.</summary>
        /// <param name="queue">The queue is intialized with a shalled-copy of this queue.</param>
        public PriorityQueue(PriorityQueue queue) {
            _heap = queue._heap.Clone();
        }
        #endregion

        #region Methods
        /// <summary>Enqueues an item to the priority queue.</summary>
        /// <param name="priority">The priority of the object to be enqueued.</param>
        /// <param name="value">The object to be enqueued.</param>
        public virtual void Enqueue(int priority, object value) {
            _heap.Insert(priority, value);
        }

        /// <summary>Dequeues an object from the priority queue.</summary>
        /// <returns>The top item (max priority) from the queue.</returns>
        public virtual object Dequeue() {
            return _heap.Remove();
        }

        /// <summary>Empties the queue.</summary>
        public virtual void Clear() {
            _heap.Clear();
        }
        #endregion

        #region Implementation of ICollection
        /// <summary>Copies the priority queue to an array.</summary>
        /// <param name="array">The array to which the queue should be copied.</param>
        /// <param name="index">The starting index.</param>
        public virtual void CopyTo(System.Array array, int index) { _heap.CopyTo(array, index); }

        /// <summary>Determines whether the priority queue is synchronized.</summary>
        public virtual bool IsSynchronized { get { return _heap.IsSynchronized; } }

        /// <summary>Gets the number of items in the queue.</summary>
        public virtual int Count { get { return _heap.Count; } }

        /// <summary>Gets the synchronization root object for the queue.</summary>
        public object SyncRoot { get { return _heap.SyncRoot; } }
        #endregion

        #region Implementation of IEnumerable
        /// <summary>Gets the enumerator for the queue.</summary>
        /// <returns>An enumerator for the queue.</returns>
        public IEnumerator GetEnumerator() { return _heap.GetEnumerator(); }
        #endregion

        #region Synchronization
        /// <summary>Returns a synchronized wrapper around the queue.</summary>
        /// <param name="queue">The queue to be synchronized.</param>
        /// <returns>A synchronized priority queue.</returns>
        public static PriorityQueue Synchronize(PriorityQueue queue) {
            // Return the queue if it is already synchronized.  Otherwise, wrap it
            // with a synchronized wrapper.
            if(queue is SyncPriorityQueue) return queue;
            return new SyncPriorityQueue(queue);
        }
        #endregion

        /// <summary>A synchronized PriorityQueue.</summary>
        public class SyncPriorityQueue : PriorityQueue {
            #region Construction
            /// <summary>Initialize the priority queue.</summary>
            /// <param name="queue">The queue to be synchronized.</param>
            internal SyncPriorityQueue(PriorityQueue queue) {
                // NOTE: We're synchronizing just be using a synchronized heap!
                // This implementation will need to change if we get more state.
                if(!(_heap is BinaryHeap.SyncBinaryHeap)) {
                    _heap = BinaryHeap.Synchronize(_heap);
                }
            }
            #endregion
        }
    }
    #endregion



    #region MyRegion

    public abstract class PriorityQueueBase<T> : IComparer<T>, ICollection, IEnumerable<T>, IEnumerable {
        private List<T> _items;
        private int _rank;

        protected virtual int this[T item] {
            get {
                for(int i = 0; i < this._items.Count; i++) {
                    if(this._items[i].Equals(item)) {
                        return i;
                    }
                }
                return -1;
            }
            set { }
        }

        #region IComparer<T> Members

        public abstract int Compare(T a, T b);

        #endregion

        private PriorityQueueBase() { }

        protected PriorityQueueBase(int rank) {
            if(rank < 2) {
                throw new Exception();
            }
            this._items = new List<T>();
            this._rank = rank;
        }

        public int Rank {
            get {
                return this._rank;
            }
        }

        public int Count {
            get {
                return this._items.Count;
            }
        }

        private T this[int index] {
            get {
                return this._items[index];
            }
            set {
                this._items[index] = value;
                this[value] = index;
            }
        }

        private int GetParentIndex(int index) {
            if(index > 0) {
                return (index - 1) / this._rank;
            }
            return -1;
        }

        private int GetFirstChildIndex(int index) {
            int firstChildIndex = index * this._rank + 1;
            if(firstChildIndex < this._items.Count) {
                return firstChildIndex;
            }
            return -1;
        }

        private int GetNextSiblingIndex(int index) {
            if((index % this._rank) > 0) {
                int nextSiblingIndex = index + 1;
                if(nextSiblingIndex < this._items.Count) {
                    return nextSiblingIndex;
                }
            }
            return -1;
        }

        private int GetMaxChildIndex(int index) {
            int maxChildIndex = this.GetFirstChildIndex(index);

            if(maxChildIndex > 0) {
                for(int siblingIndex = this.GetNextSiblingIndex(maxChildIndex); siblingIndex > 0; siblingIndex = this.GetNextSiblingIndex(siblingIndex)) {
                    if(this.Compare(this[siblingIndex], this[maxChildIndex]) > 0) {
                        maxChildIndex = siblingIndex;
                    }
                }
            }

            return maxChildIndex;
        }

        private void Requeue(int index) {
            T item = this[index];
            int newIndex = index;

            while(true) {
                int parentIndex = this.GetParentIndex(newIndex);
                if(parentIndex >= 0) {
                    T parent = this[parentIndex];
                    if(this.Compare(item, parent) > 0) {
                        this[newIndex] = parent;
                        newIndex = parentIndex;
                        continue;
                    }
                }
                break;
            }

            if(newIndex == index) {
                while(true) {
                    int childIndex = this.GetMaxChildIndex(index);
                    if(childIndex > 0) {
                        T child = this[childIndex];
                        if(this.Compare(child, item) > 0) {
                            this[newIndex] = child;
                            newIndex = childIndex;
                            continue;
                        }
                    }
                    break;
                }
            }

            if(newIndex != index) {
                this[newIndex] = item;
            }
        }

        public void Requeue(T item) {
            int index;
            if(this.Contains(item, out index)) {
                this.Requeue(index);
            }
        }

        public void Requeue(IEnumerable<T> items) {
            List<T> sortedItems = new List<T>(items);
            sortedItems.Sort(this);
            for(int i = sortedItems.Count - 1; i >= 0; i--) {
                this.Requeue(sortedItems[i]);
            }
        }

        public void Requeue(params T[] items) {
            this.Requeue(items as IEnumerable<T>);
        }

        private bool Contains(T item, out int index) {
            index = this[item];
            return index >= 0 && index < this._items.Count && object.ReferenceEquals(item, this[index]);
        }

        public bool Contains(T item) {
            int index;
            return this.Contains(item, out index);
        }

        public void Replace(T item, T newItem) {
            int index;
            if(!this.Contains(newItem, out index)) {
                if(this.Contains(item, out index)) {
                    this[index] = newItem;
                    this.Requeue(index);
                }
            }
        }

        public void Enqueue(T item) {
            int index;
            if(!this.Contains(item, out index)) {
                index = this._items.Count;
                this._items.Add(item);
                this[item] = index;
            }
            this.Requeue(index);
        }

        public void Enqueue(IEnumerable<T> items) {
            foreach(T item in items) {
                this.Enqueue(item);
            }
        }

        public void Dequeue(T item) {
            int index;
            if(this.Contains(item, out index)) {
                int lastIndex = this._items.Count - 1;
                if(index == lastIndex) {
                    this._items.RemoveAt(index);
                } else {
                    this[index] = this[lastIndex];
                    this._items.RemoveAt(lastIndex);
                    this.Requeue(index);
                }
                this[item] = -1;
            }
        }

        public void Dequeue(IEnumerable<T> items) {
            foreach(T item in items) {
                this.Dequeue(item);
            }
        }

        public bool Peek(out T item) {
            if(this._items.Count > 0) {
                item = this[0];
                return true;
            }

            item = default(T);
            return false;
        }

        public IEnumerable<T> Peek() {
            if(this._items.Count > 0) {
                for(int index = 0; true; ) {
                    int nextIndex;

                    if(this.Compare(this[index], this[0]) == 0) {
                        yield return this[index];

                        if((nextIndex = this.GetFirstChildIndex(index)) > 0) {
                            index = nextIndex;
                            continue;
                        }
                    }

                    if((nextIndex = this.GetNextSiblingIndex(index)) > 0 || (nextIndex = this.GetNextSiblingIndex(this.GetParentIndex(index))) > 0) {
                        index = nextIndex;
                        continue;
                    }

                    break;
                }
            }
        }

        public void Clear() {
            this._items.Clear();
        }

        public void TrimExcess() {
            this._items.TrimExcess();
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator() {
            return this._items.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator() {
            return this._items.GetEnumerator();
        }

        #endregion


        #region ICollection Members

        void ICollection.CopyTo(Array array, int index) {
            (this._items as ICollection).CopyTo(array, index);
        }

        bool ICollection.IsSynchronized {
            get {
                return (this._items as ICollection).IsSynchronized;
            }
        }

        object ICollection.SyncRoot {
            get {
                return (this._items as ICollection).SyncRoot;
            }
        }

        #endregion
    }

    #endregion

}
